|
Bijective numeration is any numeral system in which every non-negative integer can be represented in exactly one way using a finite string of digits. The name derives from this bijection (one-to-one correspondence) between the set of non-negative integers and the set of finite strings using a finite set of symbols (the "digits"). Most ordinary numeral systems, such as the common decimal system, are not bijective because more than one string of digits can represent the same positive integer. In particular, adding leading zeroes does not change the value represented, so "1", "01" and "001" all represent the number one. Even though only the first is usual, the fact that the others are possible means that decimal is not bijective. However, unary, with only one digit, ''is'' bijective. A bijective base-''k'' numeration is a bijective positional notation. It uses a string of digits from the set (where ''k'' ≥ 1) to encode each positive integer; a digit's position in the string defines its value as a multiple of a power of ''k''. calls this notation ''k''-adic, but it should not be confused with the ''p''-adic numbers: bijective numerals are a system for representing ordinary integers by finite strings of nonzero digits, whereas the ''p''-adic numbers are a system of mathematical values that contain the integers as a subset and may need infinite sequences of digits in any numerical representation. ==Definition== The base-''k'' bijective numeration system uses the digit-set (''k'' ≥ 1) to uniquely represent every non-negative integer, as follows: * The integer zero is represented by the ''empty string''. * The integer represented by the nonempty digit-string :: :is ::. * The digit-string representing the integer ''m'' > 0 is :: :where :: :and ::, : being the least integer not less than ''x'' (the ceiling function). ==Properties of bijective base-''k'' numerals== For a given base ''k'' ≥ 1, * there are exactly ''k''''n'' bijective base-''k'' numerals of length ''n'' ≥ 0. * if ''k'' > 1, the number of digits in the bijective base-''k'' numeral representing a nonnegative integer ''n'' is , in contrast to for ordinary base-k numerals; if ''k'' = 1 (i.e., unary), then the number of digits is just ''n''; * a list of bijective base-''k'' numerals, in natural order of the integers represented, is automatically in shortlex order (shortest first, lexicographical within each length). Thus, using λ to denote the empty string, the base 1, 2, 3, and 10 numerals are as follows (where the ordinary binary and decimal representations are listed for comparison): 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bijective numeration」の詳細全文を読む スポンサード リンク
|